1. Field of the Invention
The present invention relates to interconnect logic for a data processing apparatus, and in particular to techniques for controlling reordering of transactions between master logic units and slave logic units coupled to the interconnect logic.
2. Description of the Prior Art
Within a data processing apparatus having a plurality of master logic units and slave logic units, it is known to provide interconnect logic for coupling the master logic units and the slave logic units to enable transactions to be performed. Each transaction consists of an address transfer from a master logic unit to a slave logic unit, and one or more data transfers between that master logic unit and that slave logic unit. For a write transaction these data transfers will pass from the master logic unit to the slave logic unit (in some implementations there will additionally be a write response transfer from the slave logic unit to the master logic unit), whilst for a read transaction these data transfers will pass from the slave logic unit to the master logic unit. Any transfers from a slave logic unit to a master logic unit are referred to herein as response transfers.
The interconnect logic will provide a plurality of connection paths for coupling the various master logic units and slave logic units. The way in which the various transfers are routed via those connection paths will be dependent on the bus protocol employed within the interconnect logic. One known type of bus protocol is the non-split transaction protocol, such as is employed within a data processing apparatus having an AHB bus designed in accordance with the AHB bus protocol developed by ARM Limited, Cambridge, United Kingdom. In accordance with such a non-split transaction protocol, there is a fixed timing relationship between the address transfer of a transaction and the subsequent one or more data transfers of that transaction. In particular, the data transfer starts in the cycle following that in which the address is transferred. Due to the fixed timing relationship between the address transfers and data transfers, then it will be appreciated that the data transfers of multiple transactions occur in the same order as the address transfers.
As interconnect logic increases in complexity, due to the need to support the interconnection of a larger number of master and slave logic units, then another type of bus protocol has been developed known as a split transaction protocol. In accordance with such a split transaction protocol, the plurality of connection paths within the interconnect logic provide at least one address channel for carrying address transfers and at least one data channel for carrying data transfers. An example of such a split transaction protocol is the AXI (Advanced eXtensible Interface) protocol developed by ARM Limited, Cambridge, United Kingdom. The AXI protocol provides a number of channels over which information and data can be transferred, these channels comprising a read address channel for carrying address transfers of read transactions, a write address channel for carrying address transfers of write transactions, a write data channel for carrying data transfers of write transactions, a read data channel for carrying data transfers of read transactions, and a write response channel for returning transaction status information to the master logic unit at the end of a write transaction, such transaction status information indicating for example whether the transaction completed successfully, or whether an error occurred, etc. Use of such a split transaction protocol can increase the performance of a system compared with a similar system using a non-split transaction protocol.
Conventionally, when adopting such a split transaction protocol, data transfers over a data channel are prioritised according to the temporal ordering of the corresponding address transfers over the relevant address channel, such that data pertaining to earlier addresses (i.e. addresses transferred earlier over the address channel) are given priority over data pertaining to later addresses.
An enhancement that may be used to allow some local re-ordering of transactions at a particular slave logic unit when using interconnect logic conforming to such a split transaction protocol is described in U.S. patent application Ser. No. 10/743,537 filed on 23 Dec. 2003, for which ARM Limited is the assignee, the entire contents of which are herein incorporated by reference. In accordance with the teaching of this patent application, each address transfer includes a source identifier identifying the source of the transaction. Preferably, each master logic unit has a plurality of possible source identifiers that can be associated with transactions that it issues. This has the advantage that, for example, transactions generated by different applications running on the same processor can be distinguished so that transaction sequences from each application can be independently ordered in cases where the processes themselves are independent of each other. A slave device can then perform some local reordering of pending transactions it has to service based on such source identifier information, such that, for example, the one or more data transfers associated with a transaction issued with a particular source identifier can be given priority over the one or more data transfers associated with an earlier pending transaction issued with a different, lower priority, source identifier.
Hence, whilst for any particular transaction, the slave device is required to issue any response transfers in order, if the slave device has two pending transactions which have different transaction identifiers, it can choose which transaction to process first. Whilst this enables different priorities to be given to different master logic units, or even to particular applications running on a particular master logic unit, it can give rise to a potential cyclic dependency deadlock occurring within the interconnect logic. In particular, if at least some master logic units can issue multiple pending transactions to more than one slave device, then situations can arise where a transaction with a particular transaction identifier is issued to one slave device (which for clarity we will call slave 1), whilst another transaction with the same transaction identifier is then issued to another slave device (which for clarity we will call slave 2). The bus protocol will typically require that for transactions having the same transaction identifier, the transactions must be processed in order. However, individual slave logic units do not communicate with each other, and if those slave logic units individually have the ability to reorder transactions that have different transaction identifiers, it is possible that slave 2 that received the later transaction with the same transaction identifier issues a response transfer prior to slave 1 that received the earlier transaction with that transaction identifier. At this point, slave 2 cannot take any further action until that response transfer is accepted by the interconnect logic for routing to the master logic unit associated with the transaction, but the interconnect logic cannot accept that response transfer, because first it needs to receive the response transfer or response transfers associated with the earlier transaction issued with the same transaction identifier to slave 1. This causes slave 2 to become blocked, since it cannot de-assert the response and cannot continue processing until the response is accepted by the interconnect logic.
This may in itself be sufficient to cause deadlock, if for example slave 1 is currently blocked trying to output a response for a transaction which is later than a transaction with the same transaction identifier already issued to slave 2 but demoted by slave 2 due to reordering. This scenario is illustrated by the following example sequence of four transactions, where the two transactions issued by master 1 have the same transaction identifier and similarly the two transactions issued by master 2 have the same transaction identifier:
M1 -> S2M1 -> S1M2 -> S1M2 -> S2
This causes the transactions to be sequenced with the two slaves as follows:
S1: M1.2 M2.1S2: M1.1 M2.2
In the above, the suffix “.1” means first transaction from the associated master, and “.2” means second transaction from the associated master, such that for example “M1.1” means the first transaction from master 1. If slave 2 reorders its two transactions, then it can be seen that both slave 1 and slave 2 are trying to issues a response transfer in connection with the second transaction from a master, both of which are blocked since the masters will need to receive the response transfer(s) associated with their first transactions first.
The possibilities for deadlock become even more likely when multiple of the slave devices have the capability to reorder.
When deadlock occurs, it is often very difficult to restore the interconnect logic to a normal operating state. Therefore, when deadlock occurs it is generally required that the configuration of the interconnect be reset, which will also typically impact the operation of logic units coupled thereto. Hence, these logic units may also need to be reset to enable the required data transfers to be performed or completed. Accordingly, it will be appreciated that deadlock can have a devastating impact on the performance of a data processing apparatus.
A number of deadlock avoidance schemes have been developed which seek to reduce or remove the likelihood of a deadlock occurring. One such scheme is referred to as a “single slave” scheme, which is a scheme adopted at each master logic unit. In accordance with this scheme, a master logic unit can issue as many pending transactions as it desires to an individual slave logic unit, and these transactions can have the same or different transaction identifiers. However, for any particular transaction identifier, the master logic unit is only allowed to have transactions with that transaction identifier pending with one slave logic unit at a time. Only when those transaction have been completed can the transaction identifier be reused in connection with transactions issued to a different slave device. Accordingly, by this approach, the situation is avoided where two transactions having the same transaction identifier are issued to multiple slave devices at the same time.
In accordance with an alternative scheme, referred to as a “unique ID” scheme, each master logic unit is constrained to always use different identifiers for transactions issued to different slave logic units, again this preventing this situation where multiple transactions with the same identifier are pending with different slave logic units.
In accordance with a third type of scheme, referred to as a “cyclic order” scheme, an arbitrary order is assigned to the plurality of slave logic units coupled to the interconnect logic. Each master logic unit is then constrained to send transactions to the various slave logic units in that predefined arbitrary order. Hence, by way of example, if the predefined order was slave zero, slave two, slave one, then each master logic unit can issue an arbitrary number of transactions to slave zero, followed by an arbitrary number of transactions to slave two, followed by an arbitrary number of transactions to slave one. Thereafter, all pending transactions have to be completed before that master logic unit can then again start sending transactions to slave zero.
Whilst all of these techniques are effective at reducing or removing the risk of deadlock occurring, they all place significant constraints on how each master logic unit can behave.
U.S. patent application Ser. No. 10/953,500 filed on 30 Sep. 2004, for which ARM Limited is the assignee, the entire contents of which are herein incorporated by reference, describes providing the interconnect logic with deadlock prediction logic which, at the time each address transfer is issued by a master logic unit, seeks to determine whether propagation of that address transfer may cause the interconnect logic to become deadlocked, and if so to prevent the propagation of that address transfer. The prediction logic can take regard of deadlock avoidance schemes such as those mentioned earlier when deciding whether any particular address transfer is safe or instead may cause deadlock problems. Again, this scheme restricts the flexibility of the master logic units when issuing transactions, since certain address transfers will be prevented from being propagated if the prediction logic predicts that a deadlock may arise. Further, such a scheme is relatively complex in that it requires the provision of such prediction logic.
As an alternative to the above types of schemes, another possibility that may be used in accordance with some bus protocols is to make use of a timeout mechanism to recover from deadlock situations after they occur. However, as will be appreciated from the earlier discussion of deadlocks, such deadlocks can significantly impact the performance of the data processing apparatus, and the steps required to recover from a deadlock are significant. Accordingly, it is generally felt desirable to provide schemes for seeking to avoid deadlocks occurring, rather than rely on mechanisms to recover from deadlocks after they have occurred.
Accordingly, it would be desirable to provide an improved technique for controlling the above described cyclic dependency deadlock problem, which does not require constraining the way in which individual master logic units issue transactions.